 1.动态规划之案例二
   
   最大的连续子序列和
   题目：
   给定一个长度为 n 的整数序列，求它的最大连续子序列和
   –2、1、–3、4、–1、2、1、–5、4 的最大连续子序列和是 4 + (–1) + 2 + 1 = 6
       定义状态
       dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）
       初始状态
       dp(0)=nums[0]
       状态转移方程
	     如果以 nums[0] –2 结尾，则最大连续子序列是 –2，所以 dp(0) = –2
         如果以 nums[1] 1 结尾，则最大连续子序列是 1，所以 dp(1) = 1
         如果以 nums[2] –3 结尾，则最大连续子序列是 1、–3，所以 dp(2) = dp(1) + (–3) = –2
         如果以 nums[3] 4 结尾，则最大连续子序列是 4，所以 dp(3) = 4
         如果以 nums[4] –1 结尾，则最大连续子序列是 4、–1，所以 dp(4) = dp(3) + (–1) = 3
         如果以 nums[5] 2 结尾，则最大连续子序列是 4、–1、2，所以 dp(5) = dp(4) + 2 = 5
         如果以 nums[6] 1 结尾，则最大连续子序列是 4、–1、2、1，所以 dp(6) = dp(5) + 1 = 6
         如果以 nums[7] –5 结尾，则最大连续子序列是 4、–1、2、1、–5，所以 dp(7) = dp(6) + (–5) = 1
         如果以 nums[8] 4 结尾，则最大连续子序列是 4、–1、2、1、–5、4，所以 dp(8) = dp(7) + 4 = 5 
		     如果 dp(i – 1) ≤ 0，那么 dp(i) = nums[i]
             如果 dp(i – 1) > 0，那么 dp(i) = dp(i – 1) + nums[i]
   最终解：
       最大连续子序列和是所有 dp(i) 中的最大值 max { dp(i) }，i ∈ [0, nums.length)
   代码
package com.lg.dp;

public class MaxSubArray {
    public static void main(String[] args) {
        int[] arr=new int[]{1, -2, 3, 4};
        System.out.println(getMaxSub(arr));
    }
    // 定义状态：dp(i):dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）
    //使用递推方式
    static int getMaxSub(int[] nums) {
        //过滤不合理值
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //准备一个数组
        int[] dp = new int[nums.length];
        //初始值
        dp[0] = nums[0];
        //遍历nums，找到每一个最大的连接序列和
        int max = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] <= 0) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            max = Math.max(dp[i], max);
        }
        return max;
    }
}
   
   优化
   使用变量替代数组
   代码实现
package com.lg.dp;

public class MaxSubArray2 {
    public static void main(String[] args) {
        int[] arr=new int[]{1, -2, 3, 4};
        System.out.println(getMaxSub(arr));
    }
    // 定义状态：dp(i):dp(i) 是以 nums[i] 结尾的最大连续子序列和（nums是整个序列）
    //使用递推方式
    static int getMaxSub(int[] nums) {
        //过滤不合理值
        if (nums == null || nums.length == 0) {
            return 0;
        }
        //准备一个变量
        int dp = nums[0];
        //遍历nums，找到每一个最大的连接序列和
        int max = dp;
        for (int i = 1; i < nums.length; i++) {
            if(dp > 0) {
                //下一个连续子序列和要加上这个遏制
                dp=dp+nums[i];
            } else {
                dp=nums[i];
            }
            max = Math.max(dp, max);
        }
        return max;
    }
}

 2.案例三
   
   最长公共子序列
   最长公共子序列（Longest Common Subsequence，LCS）
   leetcode_1143_最长公共子序列：https://leetcode-cn.com/problems/longest-common-subsequence/
   计算两个序列的最长公共子序列长度
   [1, 3, 5, 9, 10] 和 [1, 4, 9, 10] 的最长公共子序列是 [1, 9, 10]，长度为 3
   1).思路分析
   假设 2 个序列分别是 nums1、nums2
       i ∈ [0, nums1.length]
       j ∈ [0, nums2.length]
   定义状态方程
   假设 dp(i, j) 是【nums1 前 i 个元素】与【nums2 前 j 个元素】的最长公共子序列长度
   定义初始值
   dp(i, 0)、dp(0, j) 初始值均为 0
   定义状态转移方程
       假设 nums1[i – 1] = nums2[j – 1]，那么 dp(i, j) = dp(i – 1, j – 1) + 1
       假设 nums1[i – 1] ≠ nums2[j – 1]，那么 dp(i, j) = max { dp(i – 1, j), dp(i, j – 1) }
   2).第一版
   递归实现
 package com.lg.dp;

/**
 * 计算最长公共子序列
 */
public class LCS {
    public static void main(String[] args) {
        int[] arr1={1, 3, 5, 9, 10};
        int[] arr2={1, 4, 9, 10};
        System.out.println(getLCS(arr1, arr2));
    }
    //定义一个方法接收两个数组，返回两个数组的最长公共子序列
    static int getLCS(int[] arr1, int[] arr2) {
        //过滤不合理的值
        if(arr1==null || arr2==null || arr1.length==0 || arr2.length==0) {
            return 0;
        }
        return lcs(arr1, arr1.length, arr2, arr2.length);
    }

    //定义状态方程
    static int lcs(int[] arr1, int i, int[] arr2, int j) {
        //定义初始值
        if (i==0||j==0){
            return 0;
        }
        //如果arr1[i-1]=nums2[j-1]
        if (arr1[i-1]==arr2[j-1]) {
            return lcs(arr1, i-1, arr2, j-1) +1;
        } else {
            return Math.max(lcs(arr1, i-1, arr2, j), lcs(arr1, i, arr2, j-1));
        }
    }
}
  
   空间复杂度：O(k) , k = min{n, m}，n、m 是 2 个序列的长度 
   时间复杂度：O(2^n) ，当 n = m 时
   3).第二版
   使用递推实现
   代码实现
package com.lg.dp;

/**
 * 计算最长公共子序列
 */
public class LCS2 {
    public static void main(String[] args) {
        int[] arr1={1, 3, 5, 9, 10};
        int[] arr2={1, 4, 9, 10};
        System.out.println(getLCS(arr1, arr2));
    }
    //定义一个方法接收两个数组，返回两个数组的最长公共子序列
    static int getLCS(int[] arr1, int[] arr2) {
        //过滤不合理的值
        if(arr1==null || arr2==null || arr1.length==0 || arr2.length==0) {
            return 0;
        }
        //准备二维一个数组记录下子问题的解，使用递推方式自下而上计算
        int[][] dp=new int[arr1.length+1][arr2.length+1];
        for (int i = 1; i <= arr1.length; i++) {
            for (int j = 1; j <= arr2.length; j++) {
                //判断是否相等
                if (arr1[i-1]==arr2[j-1]) {
                    dp[i][j]=dp[i-1][j-1]+1;
                } else {
                    dp[i][j]=Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        return dp[arr1.length][arr2.length];
    }


}
   
   空间复杂度：O(n * m) 
   时间复杂度：O(n * m)
   非递归实现分析
   4).第三版
   使用一维数组优化
   代码实现
package com.lg.dp;

/**
 * 计算最长公共子序列
 */
public class LCS3 {
    public static void main(String[] args) {
        int[] arr1={1, 4, 5, 9, 10};
        int[] arr2={1, 4, 9, 10};
        System.out.println(getLCS(arr1, arr2));
    }
    //定义一个方法接收两个数组，返回两个数组的最长公共子序列
    static int getLCS(int[] arr1, int[] arr2) {
        //过滤不合理的值
        if(arr1==null || arr2==null || arr1.length==0 || arr2.length==0) {
            return 0;
        }
        //准备二维一个数组记录下子问题的解，使用递推方式自下而上计算
        int[] dp=new int[arr2.length+1];
        for (int i = 1; i <= arr1.length; i++) {
            int tmp=0;
            for (int j = 1; j <= arr2.length; j++) {
                //判断是否相等
                int leftTop=tmp;
                tmp=dp[j];
                if (arr1[i-1]==arr2[j-1]) {
                    dp[j]=dp[j-1]+1;
                } else {
                    dp[j]=Math.max(dp[j], dp[j-1]);
                }
            }
        }
        return dp[arr2.length];
    }
}
   
   空间复杂度优化到O(n)级别！！   